package dp;

/**
 * @author wcj
 * @Date 2021/7/6 15:08
 * @Version 1.0
 */
public class Knapsack {

    /**
     * 0-1背包问题：现有n件物品，一个容量为c的背包，物品的重量数组为w，价值数组为v，问背包能装的物品的最大价值?(每件物品只有一个)
     * 动态规划：
     * ①状态定义：dp[i][j]表示前i件物品放入到容量为j的背包的最大价值
     * ②状态转移方程：针对0-1背包问题，因为每件物品只有一个，因此只存在能放和不能放的情况
     * 若第i件物品不能放：dp[i][j] = dp[i-1][j]
     * 若第i件物品能放：dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]),j>=w[i]
     * 上面的表达式进行整合，得到如下的背包问题的通用表达式：
     * dp[i][j] = dp[i-1][j-k*w[i]]+k*v[i],0=<k<=1
     * ②状态初始化：也可以利用上面的表达式
     *
     * @param n
     * @param c
     * @param w
     * @param v
     * @return
     */
    public static int zeroAndOne(int n, int c, int[] w, int[] v) {
        int[][] dp = new int[n][c + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c + 1; j++) {
                if (i == 0) {
                    dp[i][j] = j > w[i] ? v[i] : 0;
                    continue;
                }
                if (j > w[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][c];
    }

    /**
     * 多重背包问题：n件物品，容量为c的背包，物品重量数组w，价值数组v，每件物品对应的数量数组num
     * 动态规划：
     * ①状态定义：同上
     * ②状态转移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])，0=<k<=min(j/w[i],num[i])
     * ③初始化定义：
     *
     * @param n
     * @param c
     * @param w
     * @param v
     * @param num
     * @return
     */
    public static int multiple(int n, int c, int[] w, int[] v, int[] num) {
        int[][] dp = new int[n][c + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c + 1; j++) {
                if (i == 0) {
                    dp[i][j] = Math.min(j / w[i], num[i]) * v[i];
                } else {
                    for (int k = 0; k < Math.min(j / w[i], num[i]); k++) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
                    }
                }
            }
        }
        return dp[n - 1][c];
    }

    /**
     * 完全背包问题：n件物品，容量为c的背包，物品重量数组w，物品价值数组v，每件物品的数量无限，问题同上
     * 动态规划：
     * ①状态定义：同上
     * ②状态转移方程：dp[i][j] = dp[i-1][j-k*w[i]]+k*v[i]，其中0=<k<=j/w[i]
     * ③状态初始化
     *
     * @param n
     * @param c
     * @param w
     * @param v
     * @return
     */
    public static int complete(int n, int c, int[] w, int[] v) {
        int[][] dp = new int[n][c + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c + 1; j++) {
                if (i == 0) {
                    dp[i][j] = j / w[i] * v[i];
                } else {
                    for (int k = 0; k <= (j / w[i]); k++) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
                    }
                }
            }
        }
        return dp[n - 1][c];
    }
}
